package com.study.demo.algorithm.first;

public class BinaryInsertSort {
	
	private static void binaryInsert(int[] ary) {
		for (int i = 0; i < ary.length; i++) {
			int key = 0;
			if (ary[i-1] > ary[i]) {
				key = ary[i];
			}
			int index = binarySearch(ary, ary[i], 0, i-1);
			for (int j = i-1; j > index; j--) {
				ary[j+1] = ary[j]; 
			}
			ary[index] = key;
		}
	} 

	private static int binarySearch(int[] ary, int key, int from, int to) {
		int range = to - from;
		if (range > 0) {
			int mid = (to - from)/2;
			if (ary[mid] > key) {
				return binarySearch(ary, key, from, mid-1);
			} else {
				return binarySearch(ary, key, mid+1, to);
			}
		}
		else {
			if (ary[from] <= key) {
				return from + 1;
			} else {
				return from;
			}
		}
	}
	
	
	
	
	
	
}
